%\documentclass[10pt,conference,letterpaper]{IEEEtran}
%\usepackage{times}
\documentclass{sig-alternate} %% Tighter format
%\documentclass{acm_proc_article} %% Loser format
\usepackage{latexsym}

\usepackage{amsmath,amssymb,pifont,graphicx,epstopdf,float}
\usepackage{comment,epsfig,subfigure,url,latexsym,cite}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumerate}
\newcommand{\squish}{
        \setlength{\topsep}{0pt}
        \setlength{\itemsep}{0ex}
        \vspace{-1ex}
        \setlength{\parskip}{0pt}}

\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{theorem}[lemma]{Theorem}

\title{Multi-skill Collaborative Teams based on Densest Subgraphs}
\date{}
\numberofauthors{2}
\author{
\alignauthor
Amita Gajewar \\
	\affaddr{Yahoo! Inc.}\\
	\affaddr{Santa Clara, CA, USA}\\
	\email{amitag@yahoo-inc.com}
\and
\alignauthor
Atish Das Sarma \\
       \affaddr{Georgia Institute of Technology}\\
       \affaddr{Atlanta, GA, USA}\\
       \email{atish@cc.gatech.edu}
}
%\author{%
%% author names are typeset in 11pt, which is the default size in the author block
%{Amita S. Gajewar{\small $~^{\#1}$}, Atish Das Sarma{\small $~^{*2}$} }%
%% add some space between author names and affils
%\vspace{1.6mm}\\
%\fontsize{10}{10}\selectfont\itshape
%$~^{\#}$Yahoo! Inc.\\
%701 1st Ave, Sunnyvale, CA-94089, USA\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%$~^{1}$amitag@yahoo-inc.com
%% add some space between email and affil
%\vspace{1.2mm}\\
%\fontsize{10}{10}\selectfont\rmfamily\itshape
%$~^{*}$College of Computing, Georgia Institute of Technology\\
%266 Ferst Dr., Atlanta, GA-30332, USA\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%$~^{2}$atish@cc.gatech.edu
%}

\begin{document}

\conferenceinfo{WSDM'11,} {February 9--12, 2011, Hong Kong.} 
\CopyrightYear{2011}
%\crdata{978-1-60558-889-6/10/02} 
% HOW TO GET ABOVE crdata??

\maketitle

\begin{abstract}
We consider the problem of identifying a team of skilled individuals for collaboration, in the presence of a social network. Each node in the input social network may be an expert in one or more skills - such as theory, databases or data mining. The edge weights specify the affinity or collaborative compatibility between respective nodes. Given a project that requires a set of specified number of skilled individuals in each area of expertise, the goal is to identify a team that maximizes the collaborative compatibility. For example, the requirement may be to form a team that has at least three databases experts and at least two theory experts.

The problem we study generalizes the past work of Lappas et. al [KDD 09] where only one individual of each required skill was desired in the team. Further, we explore team formation where the collaborative compatibility objective is measured as the density of the induced subgraph on selected nodes. This measure turns out to be more robust in certain aspects, compared to the previously suggested measures. This problem is NP-hard even when the team requires individuals of only one specific skill. We present a 3-approximation algorithm that improves upon a naive extension of the previously known algorithm for densest at least $k$ subgraph problem. We further show how the same approximation can be extended to the case of multiple skills as well. We also present similar results for a generalization of the previously suggested diameter based objective.

Experiments are performed on a crawl of the DBLP graph where individuals can be skilled in at most four areas - theory, databases, data mining, and artificial intelligence. 
%Our experiments corroborate the theoretical results in that the algorithm provides dense subgraphs for collaboration. 
In addition to our main algorithm, we also present and implement heuristic extensions to trade off between the size of the output and the induced density. These outperform the diameter based objective in identifying strongly cohesive teams of skilled individuals. The results also suggest solutions that are intuitively meaningful and scale well with the increase in the number of skilled individuals required. 
\end{abstract}

\section{Introduction}
We consider the problem of forming teams for collaborative projects. The set of users are presented as a social network. Each node in the network is an expert in certain skills that may be of interest to the project. Further, the edges between the nodes (which could be weighted) reflect the cohesiveness between users. Two users can collaborate better as a team if they have a high-weight edge (strong affinity for interaction and collaboration) between each other. In this setting, the problem is to identify a set of users to form a team to collaborate on a project that requires certain number of people in each of a set of specified skills.

Specifically, consider the following setting where a social network of computer scientists is presented. Each user is skilled in a subset of areas between theory, databases, data mining, and artificial intelligence. A company wants to hire people for a predetermined project. The goal of the project requires that the team contain at least three database researchers, at least two theory researchers, and at least one researcher with expertise in either data mining or artificial intelligence. What should the company do? Presented with the social network where users possess these skills and with the knowledge of their collaborative interactions, how should the company go about hiring people?

A special case of this problem was studied in~\cite{LLT}. They consider team formation when the team requires at most one person each in a set of different skills. Our problem formulation generalizes this by allowing the team to require multiple skilled individuals in any skill. Clearly there are projects where multiple people in specific skills may be desired. It turns out that this generalization makes the problem significantly harder and more interesting. For example, the problem is no longer trivial even when the social network contains users that are either skilled or not skilled in just one specific area. Suppose a project requires eight database researchers, and the social network contains people who are either skilled in databases or not, how does one go about choosing the team? We shall mention the complexity as well as algorithmic results for this special case as well shortly.

A critical question in a team formation problem based on a social network is to determine the collaborative quality of a team. The edges specify the collaborative compatibility of two nodes. However, given a subset of say $k$ nodes in the social network (let us even say these $k$ nodes are connected), how do we know how {\em collaborative} this team is? To tackle this, two objectives were suggested in~\cite{LLT}: one based on the diameter of the subgraph induced by these $k$ nodes, and another based on the spanning tree cost of these nodes. Both these objectives are {\em intuitive} and they show that meaningful results are obtained by optimizing based on these cost functions. In this paper, we suggest a density based objective. We define the collaborative affinity of a team of $k$ nodes to be proportional to the density of the induced subgraph.

Using density as a measure of the quality of an induced subgraph of nodes has certain merits over using diameter or minimum spanning tree costs. The main advantage is the {\em stability}. In the case of diameter or minimum spanning tree costs, just adding one edge between two nodes can radically change the quality of the solution. Similarly, deleting an edge can suddenly reduce the quality of a solution. However, the density of a subset of nodes is smoother in this regard. Adding an edge or deleting an edge only affects the quality of the solution to the extent of the weight of the edge (compared to the {\em total} weight of all the other edges). Also, notice that adding an edge or deleting an edge necessarily increase or decrease the quality respectively, of the solution. This seems intuitive as an added collaboration between two people in the team enhances the quality of the team. However, in the case of diameter or spanning tree costs, adding or deleting an edge may not affect the solution at all. A possible drawback, however, of density objective compared to the other two is that even a disconnected team (in terms of the induced subgraph) may have a high quality as a solution; it is not clear if this is necessary a disadvantage.

Informally, given a set of skills $1, 2, \ldots, t$, and requirements $k_1, k_2, \ldots, k_t$, the goal is to pick a subset of nodes such that at least $k_i$ distinct nodes possess skill $i$, for $1\leq i\leq t$. The same node, however, may contribute to two different skills. The objective value of the solution is the density of the induced subgraph on these nodes; the edge weights specified as a part of the input. The goal is to maximize this objective. Notice that the number of returned nodes may be as small as $k_{max} = \max_{i}{k_i}$ or be even larger than $\sum_{i}{k_i}$. We now summarize the contributions of this paper.

%****COMPLETE BELOW CONTRIBUTIONS.

\noindent{\bf Our Contributions.}

\begin{itemize}
\item We present a novel problem definition for team formation to maximize collaborative compatibility. The constraint of the problem requires the team to comprise of (at least) a specified number of skilled individuals in each of a set of skills. This generalize previous work that required forming a team with at least one skilled individual in each of a set of skills. Further, as a measure of collaborative compatibility, we suggest a density based objective. Density is a novel metric for this domain and we show that it has certain desirable properties for measuring compatibility. Our density based team formation problem also generalizes previous graph algorithms work on finding densest subgraphs with size constraints.
\item We address the collaborative team formation problem when the team requires either a single skill, or multiple skills. We show that optimizing even the special case of a single skill is  NP-hard under our density-based metric, as well as a diameter-based metric suggested previously in literature. The main theoretical result of the paper is to present a novel 3-approximation algorithm for the density based team formation problem for both single as well as multiple skills. This improves upon a naive extension of previous work on size constrained densest subgraph problems. We also show how previous work on a 2-approximation for the diameter-based team formation can be extended to our generalized problem.
\item We present several heuristic algorithms that build on our 3-approximation for density-based team formation. These algorithms trade-off between the size of the returned solution and the density, while always respecting the constraints of the skill requirements. We perform experiments on all these algorithms on the DBLP graph. Experiments show that density-based algorithms perform well in practice, identifying tightly knit and highly skilled teams. The solutions scale well with the size of the team and skill requirements. We also show through qualitative analysis that the teams suggested are intuitive and meaningful.
\end{itemize}

\noindent{\bf Overview.} We mention related work in Section~\ref{sec:rel}. The various problem definitions, notation and some properties are formalized in Section~\ref{sec:def}. Our theoretical contributions, including the main 3-approximation algorithm for our density based objective are described in Section~\ref{sec:theory1}. The theoretical work on a diameter based objective are presented in Section~\ref{sec:theory2}. Finally, some additional heuristic algorithms and experimental results on the DBLP network are detailed in Section~\ref{sec:exp}. 
%Finally, we make some concluding remarks in Section~\ref{sec:con}.

\section{Related Work}
\label{sec:rel}
Various interesting approaches for {\em team formation} have been studied over the years. In work in operations research~\cite{CL, ZK, BDD, WOMJ}, the problem is defined as finding an optimal match between people and the demanded functional requirements. It is often solved using techniques such as simulated annealing, branch-and-cut or genetic algorithms~\cite{BDD, ZK, WOMJ}. Another interesting problem formulation requires taking into consideration the psychological aspects of the individuals involved in order to form a team of efficient collaboration, e.g, the work performed by Fitzpatrick and Askin ~\cite{FA}, and Chen and Lin in~\cite{CL}. Although all these approaches are interesting, they do not use the possible presence of a social graph structure between the individuals. Therefore, these approaches should be considered complementary to ours. Further, Gaston et al.~\cite{GSJ} provides an experimental study about the effect of graph structure among individuals on the performance of the team. 

Our problem formulation differs from these fundamentally by requiring to find an optimal solution where the optimality is determined based on the properties associated with a social graph structure among the individuals. In particular, we aim to form a team that contains at least $k_i$ nodes of skill $i$ such that the density of the solution (on the subgraph induced by these individuals) is maximized. A similar problem has been addressed by Lappas et. al.~\cite{LLT}. They try to find a team that contains at least $1$ node of skill $i$ such that the result is either a minimum diameter subgraph or a minimum spanning tree. Our problem definition can be considered as an extension to this idea because we aim to find a team of $k_i$ nodes of skill $i$ instead of only $1$ node. Further, we also differ because of the density-based objectives. 
% subgraph as opposed to minimum diameter subgraph or minimum spanning tree. 

The problem of finding size-bound densest subgraphs well-studied. It is known that finding a maximum density subgraph of an undirected graph can be solved in a polynomial time~\cite{G84, L}. However, the problem of finding the maximum density subgraph with a size restriction imposed is NP-hard . In particular, finding a maximum density subgraph of size exactly $k$ is NP-hard~\cite{AHI, FKP} and no approximation scheme exists under a reasonable complexity assumption~\cite{K}.
% Recently, Andersen and Chellapilla~\cite{AC} considered approximation algorithms to this and other similar problems. 
Khuller and Saha~\cite{KS} also consider the problem of finding densest subgraphs with size restrictions and showed that these are NP-hard. Recently~\cite{KS} and Andersen and Chellapilla~\cite{AC} give constant factor approximation algorithms. Our problem definition varies from these because we not only require to find the maximum density subgraph of size at least $k$, but, we also require that this subgraph contains $k_i$ nodes of property (or skill) $i$ such that $k = k_1 + k_2 + ... + k_n$. Therefore, the past work related to finding the size-bound maximum density subgraphs is a special case of our work 

\section{Problem Definition}
\label{sec:def}

%\subsection{Notation} 
\noindent{\bf Notation.}
%
Let ${\cal X} = \lbrace 1,...,n \rbrace$ denote a set of candidates consisting of $n$ individuals. And ${\cal A} = \lbrace a_1,...,a_m \rbrace$ denotes a set of $m$ skills. Each individual $i$ is associated with a set of skills $X_i \subseteq {\cal A}$. If $a_j \in X_i$ then we say that an individual $i$ has skill $a_j$; otherwise individual $i$ does not have skill $a_j$.  Given a skill $a \in {\cal A}$, we define its support set, denoted by $S(a)$, to be the set of individuals in $\cal X$ that has this skill. That is, $S (a) = \lbrace i |  i \in {\cal X}$ and $a \in X_i \rbrace$. A task $\cal T$ is the set of paired values where each pair, $< a_j, k_j >$, specifies that at least $k_j$ individuals of skill $a_j \in {\cal A}$ are required to perform the task.  Given such task $\cal T$, a set of individuals $\cal X$ and a skill set $X_i$ for each individual, our goal is to form a team that satisfies the skill-set requirements for the task $\cal T$ and  optimize the collaborative efforts involved. 

In order to evaluate a team's collaborative compatibility, we consider the social network (graph) associated with the set of individuals $\cal X$ where each individual is represented as a node and an edge between two nodes represent the efficiency with which they can collaborate. Let $G({\cal X}, E)$ denote this undirected and weighted graph. The weight associated with each edge signifies the collaborative compatibility between the nodes they connect. We use the notations $E(G)$ and $V(G)$ to represent the edge set and vertex set associated with the graph $G$. And $W(G)$ to denote sum of the edge-weights associated with all the edges in the graph $G$ . We also define a (graph) distance function $d(i, i')$ to be the weight of the shortest path between $i$ and $i'$ in $G$. Finally, given graph $G$ and $\cal X' \subseteq X$, we use $G[\cal X']$ to denote the subgraph of $G$ that contains only the nodes in $\cal X'$. Further, without loss of generality, we assume that the graph $G$ is connected; we can transform every disconnected subgraph to a connected one by simply adding an edge that denotes zero collaborative compatibility. 

%\section{Problems}
%\subsection{Problem Definition}
\noindent{\bf Problem Definitions.} We now formalize the problems considered in this paper.

%Problem $1$ [{\it Single Skill Team Formation (sTF)}]  \\
\noindent{\bf Single Skill Team Formation (sTF).} Given a set of $n$ individuals ${\cal X} = \lbrace 1, \cdot \cdot \cdot, n \rbrace$, a graph $G({\cal X}, E)$, task ${\cal T} = \lbrace <a, k> \rbrace$, find $\cal X' \subseteq X$, such that $|{\cal X}'  \cap S(a)| \ge k$, and the collaborative compatibility $Cc(\cal X')$ is optimized. 

%Problem $2$ [{\it Multiple Skill Team Formation (mTF)}]  \\
\noindent{\bf Multiple Skill Team Formation (mTF).} Given a set of $n$ individuals ${\cal X} = \lbrace 1, \cdot \cdot \cdot, n \rbrace$, a graph $G({\cal X}, E)$, task ${\cal T} = \lbrace <a_1, k_1>, <a_2, k_2>, \cdot \cdot \cdot, <a_m, k_m> \rbrace$, find $ \cal X' \subseteq X$, such that $|{\cal X}'  \cap S(a_j)| \ge k_j$  for each $j \in \lbrace 1, \cdot \cdot \cdot, m \rbrace$ and the collaborative compatibility $Cc(\cal X')$ is optimized.

%We define the following two metrics for collaborative compatibility mentioned in the problems {\it sTF} and {\it mTF}.\\ 

The main metric that we consider for collaborative compatibility for problems {\it sTF} and {\it mTF} is the following density based objective.

\noindent{\bf Maximum Density(D).} Given a graph $G({\cal X}, E)$ and a set of individuals $\cal X' \subseteq X$, we define the density collaborative compatibility of $\cal X'$, denoted by {\it Cc-D}$(\cal X')$ to be the density of the sub-graph $G[\cal X']$. Recall that the density $d(G)$ of a graph $G$ is defined as $d(G) = \frac{W(G)}{|V(G)|}$ . The higher the value of the density, the better is the collaborative compatibility. An optimal solution $\cal X' \subseteq X$, is the team that can perform task $\cal T$ and has maximum density. 

In addition to the density objective, which is the main focus of this paper, we consider the following diameter based objective as well for comparison. A similar objective was suggested in~\cite{LLT}.

\noindent{\bf Minimum Diameter(R).} Given a graph $G({\cal X}, E)$ and a set of individuals $\cal X' \subseteq X$, we define the diameter collaborative compatibility of $\cal X'$, denoted by {\it Cc-R}$(\cal X')$, to be the diameter of the subgraph $G[\cal X']$. Recall that the diameter of a graph is the largest shortest path between any two nodes in the graph. The lower the value of the diameter, the better is the collaborative compatibility. An optimal solution $\cal X' \subseteq X$, is the team that can perform task $\cal T$ and has minimum diameter. 


In the following sections, we refer to the {\it Single Skill Team Formation (sTF)} and {\it Multiple Skill Team Formation (mTF)} problems with collaborative compatibility {\it Cc-R} as {\it Diameter-sTF} and {\it Diameter-mTF}, respectively.  Similarly, for the collaborative compatibility {\it Cc-D} we refer to the corresponding problems as {\it Density-sTF} and {\it Density-mTF} respectively.


%\subsection{Properties}
\noindent{\bf Properties.} We now describe some properties of the maximum density objective. These properties are not satisfied by the minimum diameter objective. For brevity, we mention the intuition without a rigorous definition/proof.

\noindent{\bf Monotonicity.} If a communication edge (with positive weight) is added between two nodes in the solution set for the {\it Density-sTF} or {\it Density-mTF} problem, then the collaborative compatibility objective {\it Cc-D} for the solution necessarily increases. Similarly, if a communication edge already present is deleted, then the {\it Cc-D} objective value decreases. 

\noindent{\bf Sensitivity.} The {\it Cc-D} for {\it Density-sTF} or {\it Density-mTF} does not increase or decrease radically upon adding/deleting an edge. Specifically, the {\it Cc-D} value can only increase or decrease to an extent depending on the weight of the added/deleted edge, compared to the total weight  of edges in the solution. 

Notice that neither of these properties holds on {\it Diameter-sTF} or {\it Diameter-mTF}. For example, adding or deleting an edge may not alter the diameter of the solution at all (and therefore {\it Cc-R} is not monotonic. Similarly, adding or deleting an edge can radically change the diameter (for example make it finite from infinite) for an induced subgraph; this would mean that the diameter objective is highly sensitive to small change. 

The properties for density based objectives fall out of the fact that density is {\em local} in the sense that adding or deleting edges only gradually alters the value of a solution subgraph. Diameter based objectives (or even then minimum spanning tree based objective suggested in~\cite{LLT} that we do not consider in this paper) are {\em global} in the sense that altering something locally can globally change the objective radically. These properties make density based objectives somewhat more suitable. One drawback, however, of density as an objective arises from the following property.

\noindent{\bf Connectivity.} A downside of the exact density based measure is that even the optimal solution may be a collection of disconnected components. Notice that this is not the case for the diameter based objective. We show how to overcome this difficulty in the experimental section by suggesting heuristic algorithms to ensure returning connected dense solutions. 

\section{Density-based objective}
\label{sec:theory1}

\begin{claim}
{\it Density-sTF} and {\it Density-mTF} problems are NP-complete.
\end{claim}
\begin{proof}
We prove the $claim$ by a reduction from the {\it Densest at least $k$ subgraph (DalkS)} problem defined in ~\cite{KS}. An instance of {\it DalkS} consists of a graph $G({\cal X}, E)$, and a constant $k$ and the solution is a maximum density subgraph with at least $k$ nodes. We transform it into an instance of {\it Density-sTF} problem by defining a skill $a$ for every node $v \in V$ in which case a solution would be a maximum density subgraph with at least $k$ nodes that have skill $a$. And since skill $a$ is defined for every node in $G$, it is easy to see that ${\cal X'} \subseteq {\cal X} $ is the solution to the problem {\it Density-sTF}  iff it is a solution to the problem {\it DalkS}. The problem {\it Density-sTF} is a special case of {\it Density-mTF} which implies that {\it Density-mTF} is NP-hard. 
\end{proof}

\subsection{3-approximation algorithm for {\it Density-sTF}}
In this section, we present the algorithm {\it s-DensestAlk} for the {\it Density-sTF} problem. The algorithm is an extension of the $DensestAtleastK(G, k)$ algorithm in ~\cite{KS} to calculate the maximum density subgraph containing at least $k$ vertices. We present a proof of 3-approximation for our algorithm. It is important to note that a 4-approximation can be obtained {\em easily} using the work of~\cite{KS}. In particular, they present a 2-approximation for obtaining a densest subgraph that contains at lease $k$ nodes from the entire graph $G$. Notice that if we naively add any $k$ skilled nodes to the subgraph returned by their algorithm, we get a 4-approximation. This is because adding $k$ nodes reduces the density by at most half, and the optimal solution to their problem has density at least as much as the optimal solution to {\it Density-sTF}. For brevity, we omit the proof of this observation. It turns out that proving a 3-approximation to {\it Density-sTF} is significantly harder. 

The algorithm {\it s-DensestAlk(G, {\cal T})}  accepts input parameters: graph $G$, task ${\cal T} = \lbrace <a_1, k_1> \rbrace$ where at least $k_1$ individuals/nodes of skill $a_1$ are required to perform the task ${\cal T}$. Also, in the following algorithm, the routine $shrink(G, H)$ creates a subgraph of $G$ such that, it removes $H$ from $G$ and for each $v \in (G - H)$, if $v$ has $l$ edges to the vertices in $H$, then it adds $l$ self-loops to $v$ with the corresponding edge-weights. And when we take a union of two subgraphs, say $H_1$ and $H_2$, then for each loop, we look at its corresponding edge, say $e(u, v)$, in the original graph, $G$, and if $u \in H_1, v\in H_2$ (or vice-versa), we replace the loop by an edge $e(u, v)$.

{\it Intuition.} The algorithm roughly proceeds by continuously finding the densest subgraph in the remaining graph (which can be done in polynomial time), and adds them together. This process is repeated until at least $k$ skilled nodes have been picked. Up till this step is similar to~\cite{KS}. Now, algorithm {\it s-DensestAlk} considers the resulting subgraphs at each iteration and pads it with additional skilled nodes to reach $k$ skilled nodes. This results in many candidate solutions (as many as the number of iterations); the densest of these is picked. 

We now present the approximation guarantee. While the algorithm is simple, the analysis is fairly detailed. The key idea is to consider various cases about the returned subgraph and carefully examine the density of each component. The analysis is similar to~\cite{KS} at the high level. However, the second case needs to be split into several sub-cases here to consider the number of skilled nodes added 

\begin{algorithm}{s-DensestAlk($G, {\cal T}$)}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_1)| < k_1$ where ${\cal T} = \lbrace <a_1, k_1> \rbrace$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow D_i \cup H_{i + 1}$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $n_{a1} =$ number of nodes of skill $a_1$ in $D_i$
\STATE Add $max(k_1 - n_{a1}, 0)$ nodes of skill $a_1$ to $D_i$ to form $D'_i$
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}

\begin{theorem}
The algorithm {\it s-DensestAlk} achieves an approximation factor of 3 for the {\it Density-sTF} problem.
\end{theorem}
\begin{proof}
\setcounter{equation}{0}
If the number of iterations is 1, then $H_1$ is the maximum density subgraph that contains at least $k$ nodes of skill $a$. Therefore, $H^* = H_1$ and the algorithm returns it. Otherwise, say the algorithm iterates for $l \ge 2$ rounds. There can be two cases:

\noindent {\bf Case 1:} There exists a $l' < l$ such that \\
$W(D_{l' - 1} \cap H^*) \le \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$.

\noindent {\bf Case 2:} There exists no such $l' < l$.

Before analyzing the two cases in detail, note that by construction
%, owing to the way the algorithm {\it s-DensestAlk} constructs, $D_i$ and $H_i$\\
$density(H_i) \le density(D_i) \le density(D_{i - 1})$. We now consider case 2 first and later case $1$.

\noindent {\bf Proof for Case 2.} 

Since the algorithm terminates after $l$ iterations, $D_l$ contains at least $k$ nodes of skill $a$. Further, we know that for each $j \le l - 1, W(D_j \cap  H^*)  \le \frac{W(H^*)}{2}$ \\ 
$\Rightarrow W(G_j \cap  H^*)  \ge \frac{W(H^*)}{2}$ \\ 
$\Rightarrow \frac{W(G_j \cap H^*)}{|V(G_j \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|}$ \\ 
$\Rightarrow G_j$ contains a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_l) \ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(D_l) \ge \frac{d^*}{2}$
%(The last step follows because by construction $D_l = H_1 \cup H_2 \cdot \cdot \cdot \cup H_l$) 

Thus, $D_l$ has density $\ge \frac{d^*}{2}$ and contains at least $k$ nodes of skill $a$. Therefore, the algorithm indeed returns a subgraph of density at least $\ge \frac{d^*}{2}$.

\noindent{\bf Proof for Case 1}

\noindent $W(D_{l' - 1} \cap H^*) \le \frac{W(H^*)}{2}$  and  $W(D_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$\\
$\Rightarrow W(G_{l'} \cap H^*) \ge \frac{W(H^*)}{2}$ where $G_{l'} = shrink(G, D_{l' -1})$ \\ 
$\Rightarrow \frac{W(G_{l'} \cap H^*)}{|V(G_{l'} \cap H^*)|} \ge \frac{W(H^*)}{2 |V(H^*)|} = \frac{d^*}{2}$ \\ 
$\Rightarrow G_{l'}$ has a subgraph of density $\ge \frac{d^*}{2}$ \\ 
$\Rightarrow density(H_{l'}) \ge \frac{d^*}{2}$  ($H_{l'}  \mbox { is densest subgraph of } G$) \\ 
$\Rightarrow density(D_{l'}) \ge \frac{d^*}{2}$

Now, let us divide {\bf Case 1} into following $4$ parts 
\begin{enumerate}[(a)]
\item $|V(D_{l'})| \le  \frac{k}{2}$ \\
$density(D_{l'}) = \frac{W(D_{l'})}{|V(D_{l'})|} \ge \frac{W(H^*)}{2}\frac{2}{k} \ge \frac{E(H^*)}{ |V(H^*)|} \ge d^*$ 

According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Therefore, the resulting subgraph, $D'_{l'}$ has density $d \ge \frac{d^*}{3}$.

\item $|V(D_{l'})| \ge  2k $

According to step $10$, algorithm adds at most $k$ vertices to $D_{l'}$. Further, we know that $density(D_{l'}) \ge \frac{d^*}{2}$ therefore, the resulting subgraph, $D'_{l'}$ has density 

\noindent $d = \frac{W(D_{l'})}{|V(D_{l'})| + k} \ge \frac{W(D_{l'})}{\frac{3}{2} |V(D_{l'})|}  \ge  \frac{d^*}{3}$

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $ |V(D_{l'}) \cap V(H^*)| \ge \frac{|V(H^*)|}{2}$

According to step $10$, algorithm adds at most $\frac{|V(H^*)|}{2}$ nodes to $D_{l'}$ to form $D'_{l'}$ with density, say $d$.

\begin{enumerate}[i]
\item $|V(D_{l'})| \ge |V(H^*)|$ \\
$d = \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(D_{l'})| + \frac{|V(D_{l'})|}{2}} =   \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$ 

\item $|V(D_{l'})| \le |V(H^*)|$ \\
%$d = \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge  \frac{\frac{W(H^*)}{2}}{\frac{3}{2}|V(H^*)|} \ge \frac{d^*}{3}$
$d = \frac{W(D_{l'})}{|V(D_{l'}|) + \frac{|V(H^*)|}{2}} \ge \frac{W(D_{l'})}{|V(H^*)| + \frac{|V(H^*)|}{2}} \ge \frac{d^*}{3}$
\end{enumerate} 

\item $\frac{k}{2} < |V(D_{l'})| <  2k$ and $|V(D_{l'}) \cap V(H^*)| < \frac{|V(H^*)|}{2}$

If $d_{l'} = density(D_{l'}) \ge d^*$, then adding at most $k$ vertices gives a subgraph $D'_{l'}$ with density, say $d$ such that

\noindent $d = \frac{W(D_{l'})}{ |V(D_{l'})| + k} \ge \frac{W(D_{l'})}{|V(D_{l'})| + 2 |V(D_{l'})|}  \ge \frac{W(D_{l'})}{3 |V(D_{l'})|} \ge \frac{d^*}{3}$

Therefore, $D'_{l'}$ is a subgraph that contains at least $k$ nodes of skill $a$ and has density $d \ge \frac{d^*}{3}$. We are done here.

Now, assume that $d_{l'} < d^*$.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.25, bb = 30 300 500 700]{3_approx_dia_1.eps}
\caption{$D_{l'} = D_{i1} \cup D_{i2} \cup X$}\label{fig:3approx}
\end{center}
\end{figure}
In the rest of the proof, we divide $D_{l'}$ into subgraphs as explained below and shown in Figure~\ref{fig:3approx}. 

$\mbox{Let } G' = D_{l'} \cap H^* $ \\
$\Rightarrow |V(G')| = |V(D_{l'} \cap H^*)| < \frac{|V(H^*)|}{2} $ \\ 
$\mbox {and } W(G') = W(D_{l'} \cap H^*) \ge  \frac{W(H^*)}{2} $ \\
$\Rightarrow density(G') \ge \frac{\frac{W(H^*)}{2}}{\frac{|V(H^*)|}{2}} \ge d^* $ \\
$\Rightarrow W(G') \ge \frac{W(H^*)}{2} \ge \frac {d^*|V(H^*)|}{2} $ \\
Let, $density(H_i)  > d^*$ and $density(H_{i+1}) < d^*$\\  
$\Rightarrow density(D_i)  = d_i > d^*$ 

Let, $n_i = |V(D_i)| $

If $n_i \ge \frac{|V(H^*)|}{2}$ then, add at most $k$ vertices to $D_i$ to get a subgraph $D'_i$ with $density(D'_i) = d$, such that  \\
$d = \frac{W(D_i)}{|V(D_i)| + k} \ge \frac{W(D_i)}{|V(D_i)| + |V(H^*)|} \ge \frac{W(D_i)}{3 |V(D_i)|} \ge \frac{d^*}{3}$ \\ 
Thus, $D'_i$ is a subgraph containing at least $k$ nodes of skill $a$ and density $d \ge  \frac{d^*}{3}$ and we are done here.

Now, assume that $n_i < \frac{|V(H^*)|}{2}$\\ 
We know that $G'$ is a subgraph of $D_{l'}$ with $density(G') >  d^*$, however, $density(D_{l'}) < d^*$. And we also know that $D_i$ is a subgraph of $D_{l'}$ such that $density(D_i) > d^*$ and $density(D_{i+1}) < d^*$.  Therefore, there exists a sub-graph of $G'$ that is contained in $D_i$.

Let us define \\
$D_{i1} = D_i \cap G'$  and $D_{i2} = shrink(D_i, D_{i1})$ and \\  
$G'' = shrink(G', D_{i1})$\\
$\Rightarrow G' = D_{i1} \cup G''$ \\

As proved earlier, $W(G')  \ge \frac{|V(H^*)| d^*}{2}$ \\  
$\Rightarrow W(D_{i1}) + W(G'') \ge  \frac{|V(H^*)| d^*}{2} $  \\ 
$\Rightarrow W(D_{i1}) \ge  \frac{|V(H^*)| d^*}{2} - W(G'') $

As defined earlier, $density(H_i) > d^*$ \\
$\Rightarrow$ for each $j \le i, density(H_j) > d^*$. \\ 
Further, $H_j = \mbox{ densest subgraph of } shrink(G, D_{j-1})$ \\
$\Rightarrow$ for each $v\in H_j$ or $v\in D_i$, $degree(v) > d^*$ \\
%$\Rightarrow$ for each $v \in D_i, degree(v) > d^*$ \\
$\Rightarrow density(D_{i2}) > \frac{d^*}{2}$

Now, let us define $X = shrink(D_{l'}, D_i)$; $\Rightarrow G'' \subseteq X$ \\
Further, $n_{x} = |V(X)|$, $n_{l'} = |V(D_{l'})|$, and $n'' = |V(G'')|$.

Since $H_{l'}$ is the maximum density subgraph of $shrink(G, D_{l'-1})$, for any $S \subseteq H_{l'},$ \\
$density(H_{l'})  \ge density(S)$ \\
$\Rightarrow density(H_j) \ge density(H_j \cap G'')$ (for all $j \le l'$)\\ 
Further, $X = H_{i+1} \cup H_{i + 2} \cup \cdot \cdot \cdot H_{l'}$ \\
$\Rightarrow density(X)  \ge density(G'')$ $\Rightarrow d_x \ge d''$.
%$\ge d_{x1}n_{x1} - d''n''
%\frac{d^*}{2}(n_{x1} - n'')$ \\ \\

%Now, before completing the analysis, recall 
%$V(G) = $ a vertex set of $G$ \\
%$D = $ a graph obtained by adding at most $k$ nodes of skill $a$ to $D_{l'}$ \\
%$n_{l'} = | V(D_{l'}) |$  \\  \\

We now complete the analysis. 

\noindent $d = density(D) = \frac{W(D_{l'})}{n_{l'} + k}$ \\
$\ge \frac{W(D_i) + E(X)}{n_{l'} + k}$ \\ 
$= \frac{W(D_{i1}) + W(D_{i2}) + W(X)}{n_{l'} + k}$ \\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} - W(G'') + \frac{d^*n_{i2}}{2} + d_xn_x}{n_{l'} + k}$ (Note : $d_{i2} \ge \frac{d^*}{2}$)\\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} - d''n'' +  \frac{d^*n_{i2}}{2} + d_xn_x}{n_{l'} + k}$ \\ 
%$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + d_x(n_x - n'')}{n_{l'} + k}$  (Note : $d_x \ge d''$) \\ 
$\ge \frac{\frac{d^* |V(H^*)|}{2} + \frac{d^*n_{i2}}{2} + \frac{d^*}{2}(n_x - n'')}{n _{l'}+ k}$  (Since $d_x\ge\frac{d^*}{2}$, $d_x\ge d''$, $n_x\ge n''$)\\ 
%$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i2} + n_{x} - n'' - n_{i1} + n_{i1}}{n_{l'} + k}$ \\ 
%$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i1} + n_{i2} +n_{x} - (n'' + n_{i1})}{n_{l'} + k}$ \\ 
$= \frac{d^*}{2} \frac{|V(H^*)| + n_{i1} + n_{i2} +n_{x} - |V(G')|}{n_{l'} + k}$ (Using $G' = D_{i1} \cup G''$)\\ 
$\ge \frac{d^*}{2} \frac{|V(H^*)| + n_{l'} - \frac{|V(H^*)|}{2}}{n_{l'} + k}$ (Note: $|V(G')|  \le \frac{|V(H^*)|}{2}$) \\ 
%$= \frac{d^*}{4} \frac{2n_{l'} + |V(H^*)|}{n_{l'} + k}$ \\ 
%$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k}$ \\ 
$\ge \frac{d^*}{4} \frac{2n_{l'} + k}{n_{l'} + k} \ge \frac{d^*}{3}$ (apply the inequality $\frac{k}{2} < n_{l'} < 2k$).
\end{enumerate}
\end{proof}

\subsection{3-approximation algorithm for {\it Density-mTF}}
In this section, we present the algorithm {\it m-DensestAlk} for the {\it Density-mTF} problem. This is an extension of the algorithm {\it s-DensestAlk} for the {\it Density-sTF} problem presented in the previous section. The algorithm $m-DensestAlk(G, {\cal T})$  accepts input parameters: graph $G$, task ${\cal T} = \lbrace <a_1, k_1>, <a_2, k_2>, \cdot \cdot \cdot, <a_m k_m>\rbrace$  which requires at least $k_i$ individuals of skill $a_i$ to perform the task $\cal T$.

\begin{algorithm}{m-DensestAlk($G, {\cal T}$)}
\begin{algorithmic}[1]
\STATE $D_0  \leftarrow \phi, \ G_0 \leftarrow G, \ i \leftarrow 0$
\WHILE{ $|D_i \cap S(a_j)| < k_j$ for any $<a_j, k_j> \in {\cal T}$}
\STATE $H_{i + 1} \leftarrow$ maximum-density-subgraph$(G_i)$
\STATE $D_{i + 1} \leftarrow D_i \cup H_{i + 1}$
\STATE $G_{i + 1} \leftarrow shrink(G_i,  H_{i + 1})$
\STATE $i \leftarrow i + 1$
\ENDWHILE
\FOR {$each \ D_i$}
\STATE $D'_i \leftarrow D_i$
\FOR {$each \ <a_j, k_j> \in {\cal T}$}
\STATE $n_{aj} =$ number of nodes of skill $a_j$ in $D_i$
\STATE Add $max(k_j - n_{aj}, 0)$ nodes of skill $a_j$ to $D'_i$
\ENDFOR
\ENDFOR
\STATE Return $D'_i$ which has the maximum density
\end{algorithmic}
\end{algorithm}

\begin{theorem}
The algorithm {\it m-DensestAlk} achieves an approximation factor of 3 for the {\it Density-mTF} problem.
\end{theorem}
\begin{proof}
Let $k = \sum_{j=1}^{m}{k_j}$ where $k_j$ indicates the number of individuals required of skill $<a_j, k_j> \in {\cal T} \ (1 \le j \le |{\cal T}|)$. Therefore, an optimal solution, $H^*$, has at least $k$ vertices. The proof for {\it m-DensestAlk} is analogous to the proof for {\it s-DensestAlk} with the only difference that instead of adding any $k$ nodes of skill $a$ to $D_i$s, we add $k_j$ nodes of skill $a_j \in {\cal T} \ (1 \le j \le |{\cal T}|)$.
\end{proof}

{\it Time Complexity.} In the algorithm {\it s-DensestAlk}, the while loop in line $2$ iterates at most $n = |V(G)|$ times. In each iteration, the densest subgraph is computed using the algorithm in Goldberg~\cite{G84} which runs in time $O(n^3 \log{n})$. So, the total time spent in constructing all $D_i$s (lines $2$-$7$) is $O(n^4 \log n)$. This dominates the time required to construct all $D'_i$s and to choose the densest of them (lines $8$-$12$). Similarly, 
%in {\it MultiiSkillDensestAtleastK}, the time required to construct all $D'_i$s and also to choose the one with maximum density (lines $8$-$15$)  is $O(n|{\cal T}|)$. Therefore, 
the running time of algorithm {\it m-DensestAlk} is also $O(n^4 \log n)$. In practice, however, both these algorithms are likely to run significantly faster; in particular, since the size of the returned subgraph is fairly small (let us say $O(k)$ and independent of $n$), the time complexity is more like $O(n^3k)$. 

{\it Comment.} $O(n^3)$ can still be inefficient for very large graphs but is manageable at the scale at which we run experiments. There is a linear time 3-approximation algorithm for the densest at least $k$ subgraph problem suggested in~\cite{KS,AC} but this would only translate to a $6$-approximation algorithm for {\it Density-sTF}. Similarly, directly using the $O(n^3)$-time $2$-approximation algorithm from~\cite{KS,AC} would also result in a weaker bound (i.e. $4$-approximation) for {\it Density-sTF} or {\it Density-mTF}. Therefore, the extra computation performed in considering several solutions by modifying subgraphs from each of the iterations (and then picking the best) is beneficial in obtaining the improved $3$-approximation. 

Note that the resulting solution may however be large compared to $k$, and may also be disconnected. Later in Section~\ref{sec:exp}, we present heuristic post-processing steps on this algorithm to ensure a connected and sufficiently small solution (without compromising on the constraint on skilled nodes). We also show that this does not affect the resulting density significantly.

\section{Diameter-based objective}
\label{sec:theory2}
In this section, we consider the {\it Diameter-sTF} and {\it Diameter-mTF} objectives. We begin by proving the NP-hardness of these problems. Note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work.  

\subsection{Claims}
\begin{claim} 
{\it Diameter-sTF} and {\it Diameter-mTF} problems are NP-complete.
\end{claim}
\begin{proof}
The problem {\it Diameter-sTF} is in NP. We prove that it is NP-hard by reduction from the 3-satisfiability problem. Consider a 3-SAT instance, say $\phi = C_1 \wedge C_2 ... \wedge C_m$, where each clause, $C_j = x \vee y \vee z$, and $\lbrace x, y, z \rbrace \in U = \lbrace u_1, \neg u_1, u_2, \neg u_2, \cdot \cdot \cdot, u_n, \neg u_n \rbrace$. Let, $C = \lbrace  C_1, C_2, \cdot \cdot \cdot, C_m \rbrace$. We construct an instance of {\it Diameter-sTF} problem corresponding to the 3-SAT instance $\phi$.

For each $u_i, \neg u_i \in U$, create two corresponding nodes in $G$. For each clause $C_j = x \vee y \vee z$, create five nodes in $G$, say $C_{j1}, C_{j2}, Cx_{j}, Cy_{j}, Cz_{j} $.

\noindent{\it Rule $1$:} For each $u_i$ and $\neg u_i$, set $w(u_i, \neg u_i)$ = 3.

\noindent{\it Rule $2$:} For each clause $C_j = x \vee y \vee z$,  set\\ 
$w(C_{jt}, p)=1$, $w(C_{jt}, \neg p)=2$ $\forall t\in\{1, 2\}$ and $p\in\{x, y, z\}$. \\
%$w(C_{j1}, x) =  w(C_{j1}, y) = w(C_{j1}, z) = 1$ \\
%$w(C_{j2}, x) =  w(C_{j2}, y) = w(C_{j2}, z) = 1$ \\
%$w(C_{j1}, \neg x) = w(C_{j1}, \neg y) = w(C_{j1}, \neg z) = 2$. \\
%$w(C_{j2}, \neg x) = w(C_{j2}, \neg y) = w(C_{j2}, \neg z) = 2$. \\
$w(Cp_{j}, p) = w(Cp_{j}, \neg q) = 1$ $\forall p, q\in\{x, y, z\}$ and $q\neq p$.
%$w(Cx_{j}, x) = (Cx_{j}, \neg y) = w(Cx_{j}, \neg z) = 1$ \\
%$w(Cy_{j}, y) = (Cy_{j}, \neg x) = w(Cy_{j}, \neg z) = 1$ \\
%$w(Cz_{j}, z) = (Cz_{j}, \neg x) = w(Cz_{j}, \neg y) = 1$

\noindent{\it Rule $3$:} For each pair of nodes $(x, y)$ in $G$ such that if $w(x,y)$ is not set either by {\it Rule $1$} or {\it Rule $2$} then set $w(x, y) = 2$ except in the following two cases.
\begin{enumerate}
\item$x\in U$ and $y\in U$, and any pair of variables from $\lbrace x, y, \neg x, \neg y \rbrace$ appear together in some clause $C_j \in C$.
\item $x, y$ correspond to $C_{j1}, C_{j2}$ for some clause $C_j \in C$.
\end{enumerate}
For each $u_i, \neg u_i \in U$, associate a skill $a$ to node $u_i, \neg u_i$. And for each $C_j \in C$, associate a skill $a$ to the nodes $C_{j1}, C_{j2}$. Now, set  $k =  \#variables + 2 \#clauses = n + 2m$.

We claim that $\phi$ has a satisfying assignment iff $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le 2$. 

The {\it Diameter-sTF} returns a sub-graph $\cal X'$ with minimum diameter and has at least $k$ nodes with skill $a$. If $diameter({\cal X'}) \le 2$ then it contains either $u_i$ or $\neg u_i$ but not both because $d(u_i, \neg u_i) = 3$. Since $k = n + 2m$, for each variable $u_i \in U$, $\cal X'$ contains node corresponding to either $u_i$ or $\neg u_i$ (not both) and for each clause $C_j \in C$, $\cal X'$ contains nodes corresponding to $C_{j1}$ and $C_{j2}$. Now, since $diameter({\cal X'}) \le 2$, it implies that $d(C_{j1}, C_{j2}) \le 2$. Further, if $C_j = x \vee y \vee z$,  because of the way $G$ is constructed:\\
$d(C_{j1}, C_{j2})  =  d(C_{j1}, x) + d(x, C_{j2})$  \\
$= d(C_{j1}, y) + d(y, C_{j2}) = d(C_{j1}, z) + d(z, C_{j2})= 2$.

This implies that at least one of the nodes corresponding to $x, y, z$ in $C_j$ is included in the sub-graph $\cal X'$. 

If we set the corresponding variable(s) in the each clause to $1$, each clause has a satisfying assignment. Therefore, $\phi$ has a satisfying assignment.

Now, assume that $\phi$ has a satisfying assignment, then either $u_i$ or $\neg u_i$ appears in the assignment. Further, for each clause $C_j = x \vee y \vee z$, at least one of the variables is set to $1$. Then $G$ contains a subgraph $\cal X'$ corresponding to the variables such that $\cal X'$ contains $u_i$ or $\neg u_i$ and $C_{j1}, C_{j2}$. Thus, if $\phi$ has a satisfying assignment then {Diameter-sTF} returns the subgraph $\cal X'$ with $diameter({\cal X'}) \le 2$ and $|{\cal X'} \cap S(a)| = k$. 
This completes the proof. The NP-completeness of {\it Diameter-mTF} follows from {\it Diameter-sTF}. 
\end{proof}

%\begin{claim} 
%{\it Diameter-mTF} problem is NP-complete
%\end{claim}
%\begin{proof}
%We prove the $claim$ by a reduction from the {\it Diameter-TF} problem defined in ~\cite{LLT}. An instance of {\it Diameter-TF} consists of a graph $G({\cal X}, E)$ and task ${\cal T'} \subseteq \cal A$. The optimal solution to {\it Diameter-TF} is the minimum diameter subgraph $G[{\cal X'}]$ such that $X'$ contains at least one individual that has a skill $a_j$ for each $a_j \in {\cal T'}$. We transform it to {\it Diameter-mTF} problem instance that consists  of a graph $G({\cal X}, E)$  and task ${\cal T} = \lbrace < a_j, 1> \mid a_j \in {\cal T'} \rbrace$. It is easy to see that $G[\cal X']$ is the solution to the problem {\it Diameter-TF} iff it is a solution to the problem {\it Diameter-mTF}. 
%\end{proof}

%WE DON'T NEED PROOF FOR ABOVE I THINK. 

%\subsection{Algorithms for Diameter-sTF and Diameter-mTF problems}
%In this section, w

We now present an algorithm {\it MinDiameter} that can be used for both {\it Diameter-sTF} and {\it Diameter-mTF} problems. We define the $k^{th}$ shortest distance between a node $i \in {\cal X}$ and a set of nodes $\cal X' \subseteq X$ as $d_k(i, {\cal X'}, k)$. Further, we use $Path_k(i, {\cal X'}, k)$ to represent the set of nodes that are along the $k$ shortest paths from $i$ to $\cal X'$. In the algorithm {\it MinDiameter}, we assume that all pairs shortest paths are pre-computed for the nodes in the graph $G({\cal X}, E)$. Also, let $n = |{\cal X}|$ denote the number of nodes and $t = |{\cal T}|$ denote the number of skills required for the task $\cal T$. Also, let us assume that we use the hash-tables to store the attributes related to nodes and skills. And distances from each node $i$ to rest of the nodes are pre-sorted. Then, total time spent in {\it for} loops is $O(tn  +  |S(a_{rare})|tn + tn) = O(n^2)$ assuming that $t$ is constant w.r.t. $n$ and $ |S(a_{rare})|= O(n)$. 

\begin{algorithm}{MinDiameter(G, {\cal T})} 
\begin{algorithmic}[1]
\FOR{each $<a, k> \in T$}
\STATE $S(a) = \lbrace i \mid a \in X_i \rbrace$
\ENDFOR
\STATE $a_{rare} = \arg \min_{<a, k> \in T} |S(a)|$
\FOR{each $i \in S(a_{rare})$}
\FOR{each $<a, k> \in T$}
\STATE $R_{ia} = d_k(i, S(a), k)$
\ENDFOR
\STATE $R_i \leftarrow \max_a R_{ia}$
\ENDFOR
\STATE $i^* \leftarrow \arg \min R_i$
\STATE ${\cal X'} = \lbrace i^* \rbrace$
\FOR{each $<a, k> \in T$}
\STATE ${\cal X'} = {\cal X'} \cup \lbrace  Path_k(i^*, S(a), k) \rbrace$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{claim}
For any graph distance function $d$ that satisfies the triangle inequality, the algorithm {\it MinDiameter} achieves an approximation factor of $2$ for the {\it Diameter-sTF} and {\it Diameter-mTF} problems.
\end{claim}
\begin{proof}
The analysis we present here is similar to the analysis of the {\it RarestFirst} algorithm presented in ~\cite{LLT}. First, consider the solution $\cal X'$ output by the {\it MinDiameter} algorithm, and let $a_{rare} \in T$ be the skill possessed by the least number of individuals in $\cal X$. Also, let $i^*$ be the individual picked from set $S(a_{rare})$ to be included in the solution $\cal X'$. Now, consider two other skills $a_1 \ne a_2 \ne a_{rare}$ and individuals $i, i' \in \cal X$ such that $i \in S(a_1), i \not \in S(a_2)$ and $i' \not \in S(a_1), i' \in S(a_2)$. If $i, i'$ are part of the team reported by the {\it MinDiameter} algorithm, it means that $d(i^*, i) \le d_k(i^*, S(a_1), k_1)$ and $d(i^*, i') \le d_k(i^*, S(a_2), k_2)$. Due to the way the algorithm operates, we can lowerbound the Cc-R cost of the optimal solution, $\cal X^*$,  as follows: 

\begin{equation}\label{DiaBounds}
d(i^*, i) \le \mbox{Cc-R}({\cal X^*}) \mbox{ and }  d(i^*, i') \le \mbox{Cc-R}({\cal X^*})
\end{equation}
Since we have assumed that the distance function $d$ satisfies the triangle inequality, \\
$d (i, i') \le d(i, i^*) + d(i^*, i')$\\
By applying the bounds given in ~\eqref{DiaBounds}, we get the proposed approximation factor. \\
$d (i, i') \le$ Cc-R($\cal X^*) +$ Cc-R(${\cal X^*}) \le 2 \cdot $Cc-R($\cal X^*$).
\end{proof}

%\subsection{Algorithms for Mst-sTF and Mst-mTF problems}

\section{Experiments}
\label{sec:exp}
In this section, we evaluate various team formation algorithms using the scientific collaboration graph extracted from the DBLP bibliography server. We show that the density of the subgraph returned by our algorithms {\it s-DensestAlk} and {\it m-DensestAlk} perform favorably in comparison to the algorithm {\it MinDiameter}. We also show that our algorithm for density version provides high-quality results in terms of effective communication and collaboration (larger number of paths). In this section, we also present three simple heuristic extensions that can be used to process the solutions returned by {\it s-DensestAlk} and {\it m-DensestAlk}. These are designed to further improve the obtained subgraphs by reducing size and improving connectivity, while maintaining high density. 
%We demonstrate the effectiveness of these simple heuristic algorithms in order to achieve the solution that has high density, better connectivity and smaller cardinality.  
Further, examples of teams reported by our methods illustrate the effectiveness of our framework in real scenarios. 

\subsection{Experimental Setup}
We use a snapshot of the DBLP data downloaded on May 17, 2010 to create a benchmark data set for our experiments. We only keep entries of the snapshot that correspond to papers published in the domains of Database (DB), Data mining(DM), Artificial intelligence (AI) and Theory (T) conferences. For each paper, we have information about its authors, title, and venue and year of publication. We select papers from a total of $21$ conferences categorized as follows: $DB = \{\textsc{sigmod, vldb, icde, icdt, edbt, pods}\}$, $DM = \{\textsc{www, kdd, sdm, pkdd, icdm}\}$, $AI = \{\textsc{icml, ecml, colt, uai}\}$, and $T = \{\textsc{soda, focs, stoc, stacs, icalp, esa}\}$.
%$\mbox {DB} = \lbrace $ \textsc{sigmod, vldb, icde, icdt, edbt, pods} $\rbrace$, $\mbox {DM } = \lbrace $ \textsc { www, kdd, sdm, pkdd, icdm}  $\rbrace$, $\mbox {AI } = \lbrace \textsc{ icml, ecml, colt, uai } \rbrace$ and $\mbox{T } = \lbrace $ \textsc{ soda, focs, stoc, stacs, icalp, esa } $ \rbrace$. 
%We refer to the set of selected papers as the DBLP dataset. 
We now proceed to generate the input to the Team Formation Problem as follows. We define the skill set $\cal T = \{T, DB, DM, AI\}$. The set of skilled individuals $X_{dblp}$ consists of the set of authors that have at least three papers among these four domains. Further, two authors $i_1, i_2$ are connected in the graph $G_{dblp} (X_{dblp}, E)$ if they appear as co-authors in at least two papers in DBLP. The above procedure creates a set $X_{dblp}$ consisting of $6137$ individuals. The maximum component size is $3869$. We use this for all the experiments. The skill set $X_i$ of each such author $i$ is defined as $X_i = \lbrace t \mid t \in {\cal T} \ and \ P_i(t) \ne \phi \rbrace $ where $P_i(t)$ denotes the set of papers coauthored by $i$ that are published in the conferences corresponding to the domain $t$. Further, each edge $e(i_1, i_2)$ connecting  two nodes $i_1, i_2$ is assigned an edge weight depending upon the number of co-authored publications. We now specify the edge weights used.

{\it Maximum Density Team Formation.} To evaluate the algorithms {\it s-DensestAlk} and {\it m-DensestAlk}, for each edge $e(i_1, i_2)$, we set the edge weight $w(i_1, i_2) = |P_{i1} \cap P_{i2}|$, where $P_{i1}$ and $P_{i2}$ represent the set of papers published by $i_1$ and $i_2$ respectively. For the subgraph, say $G'(V', E')$ returned by these algorithms, we calculate the density, $d' = \frac{W(G')}{|V(G')|}$. Note that a different edge weight could also be chosen, such as $\frac{|P_{i1} \cap P_{i2}}{|P_{i1} \cup P_{i2}}|$. However, we wanted to associate higher weight with edges corresponding to {\em heavy} nodes. Therefore we chose $|P_{i1} \cap P_{i2}|$; as shown later, this does give us qualitatively good results.

{\it Minimum Diameter Team Formation.} To evaluate the algorithm {\it MinDiameter}, we set the edge weight $w(i_1, i_2) = 1 - \frac{|P_{i1} \cap P_{i2} |}{| P_{i1} \cup P_{i2} |}$ as suggested in the paper~\cite{LLT}.  For comparison, when a subgraph $G'(V', E')$ is returned by the {\it MinDiameter}, we compute its density by considering the induced subgraph on vertices $V''$, say $G''$ (which could contain more edges that $E'$). The density calculated is $d'' = \frac{W(G'')}{|V(G'')|}$ with edge weights $w(i_1, i_2) =  |P_{i1} \cap P_{i2}|$. 

It is to be expected that {\it MinDiameter} performs worse in terms of density as the algorithm is designed to optimize a different objective. However, we believe that density is a better suited objective for collaborative compatibility. Further, the goal of this section is to show that our density-based algorithms perform well independently. We therefore perform evaluations based on the objective as well as qualitatively. We now present the heuristic algorithms that build on algorithms {\it s-DensestAlk} and {\it m-DensestAlk}.

\subsection{Heuristic algorithms}
The objective of the problem {\it sTF-Density} and {\it mTF-Density} is to find a subgraph with maximum density such that it satisfies the skill-set requirement in order to perform the task $\cal T$. However, it does not imply the solution that is a connected subgraph. Therefore, the team formed by considering only the objective of maximum density, may very well consist of many components, thereby making meaningful collaboration in real-life difficult. This is an artifact of the objective function, rather than the algorithm. While the solutions returned by our algorithms {\it sTF-Density} and {\it mTF-Density} never had more than three components, we would like solutions with exactly one component. 
%This problem of disconnectivity is inherent due to the way we define the density of the graph and therefore, it is not really a problem introduced by poor algorithm. 
This is a motivation for heuristic improvements. A dual benefit in our suggested heuristics is that we are able to reduce the number of nodes in the returned subgraph (while respecting the constraints of the task). The hope is that these can be achieved without compromising significantly on the density.
%However, this serves as a motivation to think about the heuristics that can be applied to the solution in order to get a connected subgraph by sacrificing on the density a little. 

\begin{algorithm}{EnhanceComponent($G', a, k$)}
\begin{algorithmic}[1]
\FOR {each component $C_i \in G'$}
\STATE $C'_i \leftarrow C_i$, $N_i \leftarrow N(C_i) - C_i$ 
\STATE (note: $N(C_i)$ denotes neighbors of nodes in $C_i$)
\FOR {each node $v \in N_i$}
\IF { $| V(C'_i) \cap S(a) | \ge k$}
\STATE ${\cal C'} \leftarrow {\cal C'} \cup C'_i$
\STATE break for loop
\ENDIF
\IF {$v \in S(a)$}
\STATE $C'_i \leftarrow C'_i \cup v $
\ENDIF
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{algorithm}{EnhancedDense($G, a, k$)}
\begin{algorithmic}[1]
\STATE $G' \leftarrow  {\it s-DensestAlk}(G, a, k)$
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', a , k)$
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | C'_i |$ 
\end{algorithmic}
\end{algorithm}

We present three heuristics. The starting point of each is the solution to {\it sTF-Density} or {\it mTF-Density}, as the case may be.
We name these heuristics as {\it EnhancedDense}, {\it PartialTrimmedDense} and {\it CompleteTrimmedDense}. The basic idea behind algorithm {\it EnhancedDense} is to inspect each individual component in the solution and attempt to modify it so that it itself satisfies the skill set requirement imposed by the task $\cal T$. This is done by examining the neighbors of the nodes in the component and adding those neighbors that are skilled nodes. The heuristics {\it PartialTrimmedDense} and {\it CompleteTrimmedDense}, take as an input the components generated by the algorithm {\it EnhanceComponent} and attempt to reduce the size of each component by removing the non-skilled nodes one by one without making the component disconnected. The {\it PartialTrimmedDense}  algorithm allows at most $k$ non-skilled nodes in the component whereas {\it CompleteTrimmedDense} attempts to remove as many non-skilled nodes as possible. The smallest resulting component with the required skilled nodes is then picked. This helps reduce the size of the solution, which is now a single component, and hopefully still sufficiently dense since the heuristic started with a 3-approximation to the density objective. 
%The details of these algorithms are explained below.  

\begin{algorithm}{CompleteTrimmedDense($G, a, k$)}
\begin{algorithmic}[1]
\STATE $G' \leftarrow  {\it s-DensestAlk}(G, a, k)$
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', a , k)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow V(C_i) - S(a)$
\WHILE {$Q$ is not empty}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\ENDFOR 
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | V(C'_i) |$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}{PartialTrimmedDense($G, a, k$)}
\begin{algorithmic}[1]
\STATE $G' \leftarrow  {\it s-DensestAlk}(G, a, k)$
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', a , k)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow \lbrace u \mid u \in C'_i \mbox { and } u \not \in S(a) \rbrace$
\WHILE {$Q$ not empty and $| V(C'_i) - S(a) | > k$}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\IF {$| V(C'_i) - S(a) | > k$}
\STATE ${\cal C'} \leftarrow {\cal C'} - C'_i$
\ENDIF
\ENDFOR 
\STATE Return $\arg \max_{C'_i \in {\cal C'}} density(C'_i)$ 
\end{algorithmic}
\end{algorithm}


\begin{figure*}[t]
\begin{center}
\subfigure[$k$ vs. density]{\includegraphics[angle=270, scale=0.20]{single_skill_k_density_2.eps}}
\subfigure[$k$ vs. size]{\includegraphics[angle=270, scale=0.20]{single_skill_k_size_2.eps}}
\subfigure[$k$ vs. density per node]{\includegraphics[angle=270, scale=0.20]{single_skill_k_density_per_node_2.eps}}
\caption{single skill experiments}\label{fig:kSingle}
\end{center}
\end{figure*}

\subsection{Experimentation Analysis}
We run various experiments for both single skill and multiple skill team formation problems. We use the {\it MinDiameter} algorithm as a basis for comparison. We do not necessarily claim that one algorithm is better than another. Rather, the goal here is to provide a high density connected subgraph whose cardinality is comparable to the one returned by {\it MinDiameter}. The understanding behind this objective is that high density (consequently many edges) suggests more opportunities for meaningful and compatible collaborations. 

\subsubsection{Single Skill Team Formation}
We run the single skill experiments for $k \in \{3, 5, 7, 9, 11, 13, 15\}$. For each value of $k$, we run four experiments corresponding to each skill $a \in \{T, AI, DB, DM\}$. 
%Therefore, for each value of $k$, we have four different solutions corresponding to four different skills. 
We calculate statistics, such as density, size and number of connected components for each solution and present the mean over these four runs as the final statistic for the particular value of $k$. 

Figures~\ref{fig:kSingle}(a) and~\ref{fig:kSingle}(b) show ($k$ vs. density) and  ($k$ vs. size) plots, respectively. From these plots, we can see that the density obtained by {\it s-DensestAlk} significantly outperforms the density obtained by {\it MinDiameter} algorithm. This is of course expected. However, the downside is that the size of the solution to {\it s-DensestAlk} is also larger (and in some cases disconnected). 
%Although, this is expected because the objective of {\it MinDiameter} algorithm is to optimize  for minimum diameter and not for maximum density, these plots demonstrate that using our algorithm we have achieved the goal of finding a high density solution leading to a team with high collaborative compatibility. 
%However, like we mentioned earlier, the solution may  contain disconnected components. 
The heuristic {\it EnhancedDense} essentially adds neighbors to each component in the solution so that the resulting component satisfies the required skill-set and then picks the one with the smallest size. Therefore connectivity is guaranteed. Further, the reduction in density is not much and even the cardinality has reduced compared to the original solution. This also means that the solution returned by {\it s-DensestAlk} contained a good component to start with - by good component we mean a component that has most of the skills satisfied and has high density. Now, notice that on further applying heuristics {\it PartialTrimmedDense} and {\it CompleteTrimmedDense}, we attempt to remove the non-skilled nodes one by one from each of these enhanced components (while maintaining connectivity). As the pots show again, this serves the purpose of significantly reducing the cardinality of the solution and as a hard constraint the algorithm still satisfies the skill requirement. 
%As a final solution, {\it PartialTrimmedDense} chooses a component with maximum density and has at most $k$ non-skilled nodes. Whereas {\it CompleteTrimmedDense} attempts to remove as many non-skilled nodes as possible and picks the one with maximum density. 
It can be observed from the plots that {\it PartialTrimmedDense} has density almost equal to the {\it s-DensestAlk} and the cardinality is reduced by more than fifty percent. Further, {\it CompleteTrimmedDense} gives a solution that has cardinality almost equal to $k$ (which would be optimal), with very little reduction in density. Finally, we plot ($k$ vs. density per node) in Figure~\ref{fig:kSingle}(c). While this figure can be deduced, we present it to highlight the observation that the heuristics reduce the cardinality without compromising on the density. Notice that in this plot, {\it CompleteTrimmedDense} has the highest value of density per node, for every value of $k$. 

Given that density is intuitively a better measure of team collaboration, these results show that we are completely able to eliminate connectivity issues inherent in this objective, and output small yet sufficient, and highly collaborative (dense) teams. We now show similar experiments for multiple skill team formation.

%This implies that using these heuristic, we have completely overcome the problem of connectivity in the sense that the solution always consists of a single component and in each of these heuristics, the density is compromised by a very low factor and the cardinality is also much lower.  

\begin{figure}[h]
\begin{center}
\subfigure[$k$ vs. density]{\includegraphics[angle=270, scale=0.2]{multi_skill_k_density_int_2.eps}}
\subfigure[$k$ vs. size]{\includegraphics[angle=270, scale=0.2]{multi_skill_k_size_int_2.eps}}
\caption{multiple skills experiments}\label{fig:kMulti}
\end{center}
\end{figure}

\begin{table*} [t]
\caption{Teams reported by s-DensestAlk.}
%\caption{Teams reported by s-DensestAlk and m-DensestAlk. Column $1$ indicates the skill requirement and column $2$ specifies the authors that form the corresponding teams.}
\label{QualityAnalysis}
\begin{tabular}{lll}
Skills&Authors\\
\hline
T(3)&{\bf Prabhakar Raghavan, Ravi Kumar, Philip S. Yu}, D. Sivakumar, Sridhar Rajagopalan, Andrew Tomkins \\
DB(3)&{\bf Philip S. Yu,  Haixun Wang, Jiawei Han}, Xifeng Yan, Wei Fan, Hong Cheng, Charu C. Aggarwal\\
DM(15)&{\bf Jiawei Han, Zheng Chen, Haixun Wang, Philip S. Yu }, Amr El Abbadi, Benyu Zhang, Wei Fan, Jun Yan, \\
&Shuicheng Yan, Hong Cheng, Qiang Yang, Ning Liu, Jian Pei, Charu C. Aggarwal, Xifeng Yan, Divyakant Agrawal\\
AI(15)&{\bf Ravi Kumar, Ronald Fagin, Philip S. Yu ,  Christos Faloutsos,  Zheng Chen},\\
& {\it Wei-Ying Ma, Andrei Z. Broder, Jian-Tao Sun, Hongjun Lu}, Dou Shen,Shuicheng Yan, Anthony K. H. Tung , \\
&Wei Fan , Sridhar Rajagopalan , Qiang Yang , Eli Upfal , Andrew Tomkins , Jure Leskovec
\end{tabular}
\end{table*}

\subsubsection{Multiple Skill Team Formation}
We run the multiple skill experiments for $k \in \{3, 8, 13, 18, 23, 28 \}$ and for each run, we randomly choose $k$ skills from $\cal A = \{T, AI, DB, DM\}$. For example, when $k=3$, we may choose a skill (multi)set $\{T, T, DM\}$ which means we want a subgraph that contains at least two authors of skill T and one author of skill DM. Note that, a given author can have multiple skills and therefore the solution may consist of a subgraph whose size is less than the value of $k$. 
%Here again, we compare the solution returned by {\it maximum-density} and {\it minimum-diameter} algorithms with respect to the properties such as density, size and number of connected components. 

Figures~\ref{fig:kMulti}(a) and~\ref{fig:kMulti}(b) plot ($k$ vs. density) and  ($k$ vs. size), respectively, for multiple skill team formation experiments. 
Note that the plots for multiple skill experiments fluctuate more than single skill experiments. Also, some solutions returned are of the same size even as $k$ is increased. This is because sometimes the solution returned is satisfying different random sets picked for different values of $k$. The fluctuation is also caused by the randomness in skill requirements.

In these figures, we again see that {\it m-DensestAlk} algorithm has the highest density.
%outperforms the density obtained by {\it MultipleSkillMinDiameter} algorithm and we form a team with many opportunities for effective collaboration. 
Note that the solution with density $0$ and size $1$ corresponds to an individual that has all the required skills. 
%to perform the task $\cal T$ and therefore, it does not necessarily imply a bad solution as far as maximum-density objective is concerned.  
Further, similar to single skill experiments, we apply the heuristics mentioned earlier in order to get a connected subgraph without compromising on the density much.  Figure~\ref{fig:kMulti}(b) shows that the heuristics have been effective in reducing cardinality. In fact, the cardinality of the solution obtained by {\it CompleteTrimmedDense} is lesser than $k$ because a single individual can satisfy more than one skills. Further, for the $k\geq 13$ tasks, the density achieved by the heuristics is also close to that of {\it m-DensestAlk}. While sometimes certain heuristics have low density (e.g., $k=3$ or $k=8$), all heuristics offer a nice trade-off between size and density (and return connected solutions by design). For each value of $k$, there exists at least one solution with density close to maximum-density and small cardinality. We omit the density per node plot here due to lack of space, and because it can be deduced from Figures~\ref{fig:kMulti}(a), (b).

%Also note that for these experiments, the skills were chosen randomly and we happened to get the same solution that satisfy the multiple skills corresponding to different values of $k$ and therefore, we see the same values for size and density even if the value of $k$ increases. Also, owing to the randomness of the skills chosen and since some skills are more common than the rest, the size and therefore density of the enhanced and trimmed components may also fluctuate and not necessarily have a strong correlation with the increasing value of $k$. 


\begin{comment}
\begin{figure}
\begin{center}
\subfigure[single skill experiment]{\includegraphics[angle=270, scale=0.30]{single_skill_k_components.eps}}
\subfigure[multiple skills experiment]{\includegraphics[angle=270, scale=0.3]{multi_skill_k_components_int.eps}}
\caption{k vs. components}\label{fig:kComponents}
\end{center}
\end{figure}
\end{comment}

\begin{comment}
\begin{figure}[h]
\begin{center}
\subfigure[k vs. density per node for single skill experiment]{\includegraphics[angle=270, scale=0.30]{single_skill_k_density_per_node.eps}}
\caption{k vs. density per node}\label{fig:kDensityPerNode}
\end{center}
\end{figure}
\end{comment}

\subsection{Qualitative evidence}
To analyze the quality of the teams that are returned by our algorithms for maximum density, we refer to the {\it Most Cited Computer Science Authors} list maintained by {\it CiteSeerX} (citeseerx.ist.psu.edu/stats/authors?all=true) which contains most cited $10000$ authors. We also refer to the list {\it Central Authors: Computer Science (all-time)} published at (confsearch.org/confsearch/ca.jsp)~\cite{KW}. This list contains $1000$ researches ranked on the basis of DBLP publications.

\begin{table}[h]
\caption{Team ranks based on top-ranked authors.}
%reported by \{s/m\}-DensityAlk, CompleteTrimmedDense, and Minimum-Diameter algorithms.}
\label{RankAnalysis}
\begin{tabular}{llll}
Skills&\{s/m\}-&CompleteTrimmed&Min\\
&DensityAlk&Dense&Diameter\\
\hline
T(3)&23.42&8.11&0\\
AI(3)&20.81&17.34&0\\
DB(3)&18.25&18.25&0\\
DM(3)&18.25&18.25&0\\
T(15)&14.95&19.67&2.05\\
AI(15)&15.25&14.48&1.86\\
DB(15)&10.54&10.80&0.75\\
DM(15)&9.55&9.93&1.05\\
T(1),DB(1),&18.25&100&24.39\\
DM(1)&&&\\
T(8),AI(6),&9.49&6.3&4.1\\
DB(8),DM(6)&&&\\
\end{tabular}
\end{table}

We examine the authors of teams returned by {\it s-DensestAlk} and {\it m-DensestAlk} algorithms in order to determine how many authors in the team are among top $500$ and top $1000$ most cited authors according to the list maintained by {\it CiteSeerX}. Due to space constraints, we present only some representative lists from single skill team formation in Table~\ref{QualityAnalysis}. The lists are for $k=3$ for $T$ and $DB$, and for $k=15$ for $DM$ and $AI$.
%gives examples of some of the experiments that we conducted. In particular, first eight rows in the table contain results of single skill team formation problem for each of the skills in ${\cal A} = \lbrace T, AI, DB, DM \rbrace$ and for $k = \lbrace 3, 15 \rbrace$. The last two rows contain the information about the teams formed for multiple skill team formation problem for $k = \lbrace 3, 28 \rbrace$. We chose these values of $k$ because, they denote the minimum and maximum values of $k$ for which we have run the various sets of single and multiple skill team formation experiments. Further, in the table ~\ref{QualityAnalysis}, 
Authors in bold indicate are in the top $500$ cited, and authors in italic are in top $1000$. 
We can see from these results that in each team, we have many top cited and even the ones not on the top $1000$ list but in these teams are prolific/famous authors. These results show that teams formed by choosing the objective of maximum density subgraph are {\em intuitively} meaningful. 

A similar pattern is seen on using the second list, i.e. of top $1000$ ranked researchers~\cite{KW}. Instead of presenting another table with author names corresponding to this list, we adopt another approach for measuring quality. We determine the overall rank of a team using the ranks of the individual authors within the team. To be specific, we compute the mean reciprocal rank of all the skilled individuals in the team and report the final rank of the team as $r = 1000 \frac{\sum_{i}\frac{1}{r_i}}{n_s}$ where $r_i$ denotes the rank of a skilled individual and $n_s$ denotes the skilled individuals in the team. Similar results are observed if this quantity to include non-skilled nodes as well.
%Further, we do consider the ranks of only skilled individuals in the team because our primary interest is to find a team that satisfies the given skill-set requirements. 
We report the ranks observed in Table~\ref{RankAnalysis}. Our original algorithms for maximum density and the subsequent heuristics form a team of highly ranked authors and perform significantly better than the minimum-diameter algorithm.
The validation of these algorithms over two different qualitative approaches provides further credence to this framework of team formation using a density based objective.

{\scriptsize
\bibliographystyle{abbrv}
\bibliography{teamofexperts7}
}

\end{document}